The present invention relates to the field of computer graphics. Many computer graphic images are created by mathematically modeling the interaction of light with a three dimensional scene from a given viewpoint. This process, called rendering, generates a two-dimensional image of the scene from the given viewpoint, and is analogous to taking a photograph of a real-world scene.
As the demand for computer graphics, and in particular for real-time computer graphics, has increased, computer systems with graphics processing subsystems adapted to accelerate the rendering process have become widespread. In these computer systems, the rendering process is divided between a computer's general purpose central processing unit (CPU) and the graphics processing subsystem. Typically, the CPU performs high level operations, such as determining the position, motion, and collision of objects in a given scene. From these high level operations, the CPU generates a set of rendering commands and data defining the desired rendered image or images. For example, rendering commands and data can define scene geometry, lighting, shading, texturing, motion, and/or camera parameters for a scene. The graphics processing subsystem creates one or more rendered images from the set of rendering commands and data.
Rendered images can include both two-dimensional and three-dimensional components. For example, many computer-aided design (CAD) applications will display three-dimensional objects overlaid with two-dimensional annotations. Two dimensional annotations can include stippled or patterned lines associated with portions of the three-dimensional objects. Unlike “solid” lines, in which all the pixels on the line are turned “on,” the pixels on a stippled line turn on and off according to a repeating “stipple” pattern associated with the line. Stippled lines can include any combination of “dotted” and “dashed” line patterns.
Stippled lines are often used to convey additional information about the two- or three-dimensional information. For example, in drafting applications, lines can be used to display dimensioning information, rotational axis, and assembly relationships. Other types of applications can use lines to convey other types of information about three-dimensional objects. The use of stippled lines and the patterns associated with them can be specified by user preferences, the application, or drafting or technical standards related to the field of application use.
Complex two-dimensional annotations may include hundreds or thousands of stippled lines. Moreover, some applications create animations of two- or three-dimensional information including stippled lines. In addition, curved lines are generally made up from short straight line segments (forming “polylines”), increasing the count by tenfold, even a hundredfold. Therefore, it is important for graphics processing subsystems to draw stippled lines as efficiently as possible.
One prior method for drawing stippled lines follows the length of the stippled line from one endpoint to another, iteratively cycling through the stipple pattern and turning pixels on or off accordingly. As the stippled line must be drawn in order from one endpoint to another, rather than the order that the graphics processing subsystem normally rasterizes pixels, drawing performance is greatly reduced. Alternatively, separate hardware for drawing lines must be included, complicating the design and expanding the size of the chip. Additionally, many graphics processing subsystems have multiple rasterization pipelines running in parallel to increase drawing performance. However, because the pattern value of a pixel on the stippled line depends on the pattern value determined for the previous pixel, this method for drawing stippled lines cannot be parallelized for optimal execution by graphics processing subsystem.
It is therefore desirable to have a system and method for drawing stippled lines efficiently and in any order required by the rasterizer for optimal performance. It is further desirable to be able to parallelize drawing stippled line over multiple rasterization pipelines. Additionally, it is desirable to draw antialiased stippled lines. Furthermore, when drawing stippled polylines, which are connected groups of stippled line segments, it is desirable to preserve stipple pattern phase information between polyline segments, so that the stipple pattern transitions smoothly. Moreover, it is desirable to be able to efficiently scale stipple patterns along a stippled line.